Z algorithm
何をするの？
「文字列Sを0番目からとi番目から同時に見ていった時に、最大で何文字一致しているか」を記録した配列をO(|S|)で構築するアルゴリズム。
table:Z-example1
p o c a p o c a l a p o c a p o c a
18 0 0 0 4 0 0 0 0 0 8 0 0 0 4 0 0 0
例えば、
pocapocalapocapoca
pocapoca
は先頭から8文字一致してるので、z[10]は8になります。
もっと複雑な例を上げると、
table:Z-example2
p p p o p o p p p o p o p p p
15 2 1 0 1 0 9 2 1 0 1 0 3 2 1
pppopopppopoppp
ppopoppp
は先頭から2文字が一致しているので、z[7]は2になります。
おきもち
既にした計算結果をうまいこと活用しようぜ！
長く一致してると、中身の部分も似てくる
「にわにはにわにわとりが、にわにはにわにわとりがいる」を例に考えてみることにします。
table:途中まで埋めた
に わ に は に わ に わ と り が 、 に わ に は に わ に わ と り が い る
25 0 1 0 3 0 2 0 0 0 0 0 "11"
「にわにはにわにわとりが、に」まで計算が終了している、とします。
この"11"に注目します。この"11"は、「そこからの11文字(にわにはにわにわとりが)は最初の11文字と同じだよ〜」という意味です。色を付けて表すと、
にわにはにわにわとりが、にわにはにわにわとりがいる
の所です。ここで、この下線部分の所は一致している、というのが既に分かっているので、例えば
にわにはにわにわとりが、にわにはにわにわとりがいる
のように太線部分の最長共通接頭辞の長さが一致することが分かります。なので、「にわに」を計算するために3回比較をする必要がなくなります。
次は、hellohelloworld,hellohellohello.で考えます。
hellohelloworld,hellohellohello.
この部分は、10文字一致しています。では、右側の途中のhelloはどうなるのでしょうか。
hellohelloworld,hellohellohello.
5文字一致…かと思いきや、
hellohelloworld,hellohellohello.
10文字一致します。右側にはみ出していますね。
5文字が一致していることは保証しているが、そこから先は知らない（5文字以上一致するかも…？）
なので、水色区間が一致してても、その中身が右にはみ出る可能性があるかないかで、場合分けする必要が出てくる
実装
code:Z-algorithm.cpp
int i = 1, j = 0;
while (i < S.size()) {
while (i+j < S.size() && Sj == Si+j) ++j; // 右向きにjを伸ばしていく if (j == 0) { ++i; continue;}
int k = 1;
while (i+k < S.size() && k+Ak < j) Ai+k = Ak, ++k; // i~j間にkを走らせる i += k; j -= k;
}
i … 左端の位置
j … iからの距離
k … i~(i+j) の間を右に進んでいきながら比較する用
jは位置ではなく「iからの距離」なので、jのいる"位置"は i+j になります